package com.xz.coursearrange.GA.impl;

import com.xz.coursearrange.common.ConstantInfo;
import com.xz.coursearrange.entity.ClassTask;

import java.util.*;
import java.util.stream.IntStream;

/**
 * @Description 抽象了遗传算法本身，为接口方法提供了针对问题的实现，如交叉，变异，适应度评估和终止条件检查
 */
public class GeneticAlgorithm {
    private int populationSize; //种群规模
    private double mutationRate; //变异率
    private double crossoverRate; //交叉率
    private int elitismCount; //精英成员数

    private Random random = new Random();

    /**
     * 锦标赛选择规模
     */
    protected int tournamentSize;

    /**
     * 搜索启发方法 模拟退火
     */
    private double temperature = 1.0; //温度变量
    private final double coolingRate = 0.0001; //冷却速度  你的 模拟退火有多激进

    /**
     * 冷却温度
     */
    public void coolTemperature() {
        this.temperature *= (1 - this.getCoolingRate());
    }

    /**
     * 适应度适应度散列表
     */
    private Map<Individual, Double> fitnessHash = Collections.synchronizedMap(
            new LinkedHashMap<Individual, Double>() {
                @Override
                protected boolean removeEldestEntry(Map.Entry<Individual, Double> eldest) {
                    // store a maximum of 1000 fitness values
                    // 最多可存储 2000 个适合度值
                    return this.size() > 2000;
                }
            }
    );

    /**
     * @param classTaskList 课程任务列表
     * @return 实例化种群
     */
    public Population initPopulation(List<ClassTask> classTaskList) {
        /**
         * 初始化一个包含 N 个“课表”的种群
         * 每个 Individual 对象就是一份完整的排课方案
         * 种群中可能有 50~200 个这样的个体（根据配置）配置是2000个个体
         */
        Population population = new Population(this.populationSize, classTaskList);
        return population;
    }

    /**
     * 终止检查 到达最大世代数
     *
     * @param generationsCount
     * @param maxGenerations
     * @return
     */
    public boolean isTerminationConditionMet(int generationsCount, int maxGenerations) {
        return generationsCount > maxGenerations;
    }

    /**
     * 个体适应度评估
     *
     * @param individual
     * @return fitness 适应度
     */
    public double calculateFitness(Individual individual) {
        // stored 储存适应度
        Double storedFitness = this.fitnessHash.get(individual);
        if (storedFitness != null) {
            return storedFitness;
        }

        // 软条件 + 硬条件
        /**
         * 个体评分逻辑
         * 硬条件:必须满足的规则，一旦违反就绝对不允许，视为“解不合法”。在遗传算法中，违反硬条件的解通常会被严重扣分，甚至直接淘汰。
         * 软条件：尽量满足的规则，违反了也可以接受，但会扣点分。
         * fitness = 软约束得分 + 硬约束惩罚  : 如果某个解违反了硬条件，fitness 就会变得很低，基本无法生存下去。
         * 注：这里加分是正数，扣分是负数 → fitness 可能为负，但数值越大越好。
         */
        double fitness = GAUtils.calculateSoftValue(individual) + GAUtils.calculateHardValue(individual);
        individual.setFitness(fitness);
        // 储存适应度到散列表
        this.fitnessHash.put(individual, fitness);
        return fitness;
    }

    /**
     * 种群评估  +   并行处理
     * 评估每个课表（个体）的好坏
     * 给当前种群里的每一份课表打一个“分数”，高分意味着排得好，低分意味着冲突多、安排差。
     * 对整个种群打分 → evalPopulation(Population population)
     * @param population
     */
    public void evalPopulation(Population population) {
        // 使用并行流计算每个个体的适应度，并更新其值
        double[] fitnessSum = new double[1];
//        通过并行方式对population中的每个个体进行计算适应度值的操作。
//        IntStream.range(0, population.size())生成一个从0到population.size()-1的整数流。
//        使用parallel()将流的处理方式设置为并行，可以提高处理速度。
//        使用forEach()对流中的每个元素进行操作。
//        在操作中，首先通过population.getIndividual(i)获取第i个个体。
//        然后通过this.calculateFitness(individual)计算该个体的适应度值。
//        使用individual.setFitness(fitness)将计算得到的适应度值设置给该个体。
//        同时，将该个体的适应度值累加到fitnessSum[0]中。
        IntStream.range(0, population.size()).parallel().forEach(i -> {
            Individual individual = population.getIndividual(i);
            //每个个体调用 calculateFitness(individual) 计算适应度
            double fitness = this.calculateFitness(individual);
            individual.setFitness(fitness);
            fitnessSum[0] += fitness;
        });

        // 计算所有个体的平均适应度值
        double populationFitness = fitnessSum[0] / population.size();
        population.setPopulationFitness(populationFitness);
    }

    /**
     * 锦标赛选择：从种群中随机选出若干个个体，选出最优的那个作为“配对对象”。
     * @param population
     * @return
     */
    public Individual selectParent(Population population) {
        // Create tournament 创建锦标赛
        Population tournament = new Population(this.tournamentSize);

        // 添加随机个染色体到锦标赛
        population.shuffle();
        for (int i = 0; i < this.tournamentSize; i++) {
            Individual tournamentIndividual = population.getIndividual(i);
            tournament.setIndividual(i, tournamentIndividual);
        }

        return tournament.getFittest(0);
    }

    /**
     * 交叉
     *  for 每个位置 i：
     *     ↓
     *   取 parent1 ← 第 i 优秀课表
     *     ↓
     *   判断：是否交叉？
     *         ↓ 是                             ↓ 否
     *    选 parent2（锦标赛）              newPopulation[i] = parent1
     *         ↓
     *    crossover → offspring
     *         ↓
     *    newPopulation[i] = offspring
     *
     * 这一步，就是从已有课表中优中选优，组合生成下一代课表种群的过程，并加入了“交叉控制机制”和“精英保留机制”，
     * 让遗传算法既能跳出局部最优，又不丢失优秀解。
     * @param population
     * @return
     */
    public Population crossoverPopulation(Population population) {
        Population newPopulation = new Population(population.size());

        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            // 排序拿出适应度最高的第一个父亲
            Individual parent1 = population.getFittest(populationIndex);

            // 精英主义  populationIndex >= this.elitismCount 保存精英个体
            /**
             * 交叉操作使用温度调整交叉概率
             * 初期温度高 → 更容易交叉探索
             * 后期温度低 → 保守进化，稳定性增强
             * 如果当前个体处于非精英位，且交叉概率满足，才进行交叉
             * 精英保留	elitismCount 保留前几名原样进入下一代 ，会保留五个适应度最好地到下一个种群
             */
            if ((this.crossoverRate * this.getTemperature()) > Math.random() && populationIndex >= this.elitismCount) {
                // 找到第二个父亲，锦标赛获取
                Individual parent2 = selectParent(population);

                // 个体 交叉
                Individual child = crossoverCourseIndividual(parent1, parent2);

                // 将 offspring 添加到 新的种群中
                newPopulation.setIndividual(populationIndex, child);
            } else {
                // 如果个体不经过交叉，它就直接加入下一个种群
                //如果没有交叉（比如是精英个体），就直接复制父亲 parent1。
                newPopulation.setIndividual(populationIndex, parent1);
            }
        }

        return newPopulation;
    }

    /**
     * 打乱顺序  变异
     * 随机选择一个班级的课表打乱不固定时间的顺序
     *
     * @param parent1
     * @param parent2
     * @return
     */
    private Individual crossoverIndividual(Individual parent1, Individual parent2) {
        Individual offspring = new Individual();

        for (String classNo : parent1.getChromosome().keySet()) {
            String[] parent1Schedule = parent1.getChromosome().get(classNo);
            String[] parent2Schedule = parent2.getChromosome().get(classNo);
//            String[] offspringSchedule = new String[Individual.TOTAL_PERIODS];

            String[] offspringSchedule = random.nextBoolean() ? parent1Schedule : parent2Schedule;

            List<String> tasks = new ArrayList<>();
            // 收集非固定时间的任务
            for (int i = 0; i < Individual.TOTAL_PERIODS; i++) {
                if (offspringSchedule[i] != null && !GAUtils.cutGene(ConstantInfo.IS_FIX, offspringSchedule[i]).equals(ConstantInfo.FIX_TIME_FLAG)) {
                    tasks.add(offspringSchedule[i]);
                }
            }

            // 打乱顺序
            Collections.shuffle(tasks);

            int taskIndex = 0;
            for (int i = 0; i < Individual.TOTAL_PERIODS; i++) {
                if (parent1Schedule[i] != null && GAUtils.cutGene(ConstantInfo.IS_FIX, parent1Schedule[i]).equals(ConstantInfo.FIX_TIME_FLAG)) {
//                    offspringSchedule[i] = parent1Schedule[i];
                } else if (taskIndex < tasks.size()) {
                    offspringSchedule[i] = tasks.get(taskIndex++);
                }
            }

            offspring.getChromosome().put(classNo, offspringSchedule);
        }

        return offspring;
    }


    /**
     * 课表交换
     *
     * @param parent1
     * @param parent2
     * @return
     */
    private Individual crossoverCourseIndividual(Individual parent1, Individual parent2) {
        /**
         * 对每个班级 classNo
         * 随机选择一个父母的排课表（整张课表），直接拷贝到子代中
         * 这种生成后代方式，老师课表可能冲突，优化给每个个体新加一个hashmap表，然后每个班级维护一个老师上课时间，每次摇色子后比对，新加入的班级课程是否冲突，不冲突，使用摇色子的结果
         * 冲突判断另一个个体的班级课表加入是否冲突，都冲突按色子结果
         */
        Individual offspring = new Individual();

        for (String classNo : parent1.getChromosome().keySet()) {
            String[] parent1Schedule = parent1.getChromosome().get(classNo);
            String[] parent2Schedule = parent2.getChromosome().get(classNo);

            String[] offspringSchedule = random.nextBoolean() ? parent1Schedule : parent2Schedule;


            offspring.getChromosome().put(classNo, offspringSchedule);
        }

        return offspring;
    }

    /**
     * 变异 +   自适应变异算法 +   搜索启发方法 模拟退火
     *
     * @param population 种群  打乱顺序的变异改变太多了
     * @return
     */
    public Population mutatePopulationPlus(Population population) {
        Population newPopulation = new Population(population.size());

        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual individual = population.getIndividual(populationIndex);
            Map<String, String[]> chromosome = individual.getChromosome();
            if (populationIndex >= 20) {
                for (String classNo : chromosome.keySet()) {
                        String[] schedule = chromosome.get(classNo);
                        List<String> tasks = new ArrayList<>(); // 任务列表
                        // 收集非固定时间的任务
                        for (int i = 0; i < Individual.TOTAL_PERIODS; i++) {
                            if (schedule[i] != null && !GAUtils.cutGene(ConstantInfo.IS_FIX, schedule[i]).equals(ConstantInfo.FIX_TIME_FLAG)) {
                                tasks.add(schedule[i]);
                            }
                        }
                        // 打乱顺序
                        Collections.shuffle(tasks);

                        int taskIndex = 0;
                        for (int i = 0; i < Individual.TOTAL_PERIODS; i++) {
                            if (schedule[i] != null && GAUtils.cutGene(ConstantInfo.IS_FIX, schedule[i]).equals(ConstantInfo.FIX_TIME_FLAG)) {
                            } else if (taskIndex < tasks.size()) {
                                schedule[i] = tasks.get(taskIndex++);
                            }
                            chromosome.put(classNo, schedule);
                        }
                }
            }
            newPopulation.setIndividual(populationIndex, individual);
        }
        return newPopulation;
    }


    /**
     * 变异 +   自适应变异算法 +   搜索启发方法 模拟退火
     *
     * 对非精英个体，对其课表中非固定课程做“微小调整” → 增加搜索多样性
     * @param population 种群 （交叉后地种群）
     * @return
     */
    public Population mutatePopulation(Population population) {
        Population newPopulation = new Population(population.size());
        Random random = new Random();

        // 获取最大适应度
        double bestFitness = population.getFittest(0).getFitness();

        for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual individual = population.getIndividual(populationIndex);

            // 计算自适应变异率
            /**
             * 如果个体比平均值好 → 变异率降低（怕破坏好基因）
             * 如果个体比较差 → 变异率高（大改也没啥好损失）
             * 这是自适应机制，确保“差的课表多尝试，好的课表少打扰”
             */
            double adaptiveMutationRate = mutationRate;
            if (individual.getFitness() > population.getAvgFitness()) {
                /**
                 * 如果这个个体适应度越接近最高适应度，则分子越小，变异率越小
                 */
                double fitnessDelta1 = bestFitness - individual.getFitness();
                /**
                 * 如果最高适应度比平均适应度差距越大，变偏保守变异，最高跟平均差不多，说明种群最优解并以一定是最优解，可能陷入局部最优解便将变异率提高
                 */
                double fitnessDelta2 = bestFitness - population.getAvgFitness();
                if (fitnessDelta2 != 0) {
                    adaptiveMutationRate = (fitnessDelta1 / fitnessDelta2) * mutationRate;
                }
            }

            // 精英主义
            /**
             * 前面 N 个个体（得分最高）不做变异
             * 保证优秀解原样保留
             */
            if (populationIndex > elitismCount) {
                Map<String, String[]> chromosome = individual.getChromosome();

                for (String classNo : chromosome.keySet()) {
                    String[] schedule = chromosome.get(classNo);

                    for (int i = 0; i < Individual.TOTAL_PERIODS; i++) {
                        /**
                         * 忽略固定课表
                         */
                        if (schedule[i] != null && schedule[i].contains(ConstantInfo.FIX_TIME_FLAG)) {
                            continue;
                        }

                        // 变异 + 模拟退火
                        /**
                         * 变异操作使用温度调整变异概率
                         * 温度越高 → 更激进的“打乱”
                         * 温度越低 → 更温和地微调优化
                         *
                         * 前期提高变异率，后期为了种群收敛减少变异率,保护较优解
                         */
                        if ((adaptiveMutationRate * getTemperature()) > Math.random()) {
                            //随机交换非固定时间的两节课
                            int swapIndex = random.nextInt(Individual.TOTAL_PERIODS);
                            /**
                             * 原先改进的课时记录在这里也可以派上用场，纯随机替换，冲突率太高，可以进行比对若冲突重新摇色子，防止因为变异个体直接被淘汰
                             * 违背变异初衷寻找更优解
                             */
                            if (schedule[swapIndex] == null || !schedule[swapIndex].contains(ConstantInfo.FIX_TIME_FLAG)) {
                                String temp = schedule[i];
                                schedule[i] = schedule[swapIndex];
                                schedule[swapIndex] = temp;
                            }
                        }
                    }
                }
            }

            newPopulation.setIndividual(populationIndex, individual);
        }

        return newPopulation;
    }


    public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount, int tournamentSize) {
        this.populationSize = populationSize;
        this.mutationRate = mutationRate;
        this.crossoverRate = crossoverRate;
        this.elitismCount = elitismCount;
        this.tournamentSize = tournamentSize;
    }

    public int getPopulationSize() {
        return populationSize;
    }

    public void setPopulationSize(int populationSize) {
        this.populationSize = populationSize;
    }

    public double getMutationRate() {
        return mutationRate;
    }

    public void setMutationRate(double mutationRate) {
        this.mutationRate = mutationRate;
    }

    public double getCrossoverRate() {
        return crossoverRate;
    }

    public void setCrossoverRate(double crossoverRate) {
        this.crossoverRate = crossoverRate;
    }

    public int getElitismCount() {
        return elitismCount;
    }

    public void setElitismCount(int elitismCount) {
        this.elitismCount = elitismCount;
    }

    public double getTemperature() {
        return temperature;
    }

    public double getCoolingRate() {
        return coolingRate;
    }
}
